package priorityqueue;

import java.util.*;

public class Test {

    private static void test1() {
        int[] arr = {27, 15, 19, 18, 28, 34, 65, 49, 25, 37};
        Heap heap = new Heap();
        for (int x : arr) {
            heap.push(x);
        }
        heap.push(100);
        System.out.println(heap);
        System.out.println(heap.poll());
        System.out.println(heap);
        System.out.println(heap.peek());
        heap.sort();
        System.out.println(heap);

    }

    private static void test2() {
        int[] arr = {27, 15, 19, 18, 28, 34, 65, 49, 25, 37};
        Heap heap = new Heap();
        heap.initData(arr);
        heap.createHeap();
        System.out.println(heap);
    }

    /**
     * 测试优先级队列
     */
    private static void test3() {
        PriorityQueue<Integer> p = new PriorityQueue<>();
        p.offer(1);
        p.offer(2);
        p.offer(3);
        while (!p.isEmpty()) {
            System.out.println(p.poll());
        }
    }

    private static void test4() {
        MyPriorityQueue p = new MyPriorityQueue();
        p.push(1);
        p.push(2);
        p.push(3);
        System.out.println(p);
        p.push(5);
        System.out.println(p);
        int x = p.peekHeap();
        System.out.println(x);
        System.out.println(p);
        x = p.pollHeap();
        System.out.println(x);
        System.out.println(p);
    }

    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> m = new HashMap<>();
        for (String word : words) {
            m.put(word, m.getOrDefault(word, 0) + 1);
        }

        PriorityQueue<Map.Entry<String, Integer>> p = new PriorityQueue<>((o1, o2) -> o1.getValue() - o2.getValue());
        for (Map.Entry<String, Integer> entry : m.entrySet()) {
            if (p.size() < k) {
                p.offer(entry);
            } else {
                Map.Entry<String, Integer> top = p.peek();
                if (top.getValue().compareTo(entry.getValue()) > 0) {
                    p.poll();
                    p.offer(entry);
                } else if (top.getValue().compareTo(entry.getValue()) == 0) {
                    if (top.getKey().compareTo(entry.getKey()) > 0) {
                        p.poll();
                        p.offer(entry);
                    }
                }
            }
        }
        List<String> ret = new ArrayList<>();
        while (!p.isEmpty()) {
            ret.add(p.poll().getKey());
        }
        Collections.reverse(ret);
        return ret;
    }
    public static void main(String[] args) {
//        test1();
//        test2();
//        test3();
        test4();
    }
}
